package com.LeeCode;

import java.util.TreeSet;

/**
 * 存在重复元素 III
 */

public class Code220 {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1, 1};
        System.out.println(new Code220().containsNearbyAlmostDuplicate(nums, 3, 0));
    }

    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        int n = nums.length;

        // 使用 TreeSet 来维护一个滑动窗口内的有序集合，便于快速查找范围内的数
        TreeSet<Long> set = new TreeSet<>();

        for (int i = 0; i < n; i++) {
            // 查找当前 nums[i] 的容忍范围内最小的数（大于等于 nums[i] - valueDiff）
            Long ceiling = set.ceiling((long) nums[i] - (long) valueDiff);

            // 如果存在，并且该数 <= nums[i] + valueDiff，则满足条件
            if (ceiling != null && ceiling <= (long) nums[i] + (long) valueDiff) {
                return true;
            }

            // 将当前数字加入 TreeSet 中
            set.add((long) nums[i]);

            // 维护滑动窗口大小为 indexDiff
            // 当 i >= indexDiff 时，移除超出窗口范围的最旧元素（i - indexDiff 位置的元素）
            if (i >= indexDiff) {
                set.remove((long) nums[i - indexDiff]);
            }
        }

        // 遍历完所有元素都没有找到符合条件的 pair，返回 false
        return false;
    }
}
